package homework1_array.alg_64;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static homework1_array.Utils.printList;

public class ArrayHomework {


//    public static void main(String[] args) {
//
//        //todo 作业1：完成这个测试方法中的addByElementBySequence()方法
//        arrayAddTest();
//
//        // todo 作业2：完成这个测试类中的removeByElement()方法
//        deleteTest();
//
//    }

    static class Solution4 {
        public static int[][] generateMatrix(int n) {
            int[][] result = new int[n][n];
            int top=0;
            int bottum = n-1;
            int left = 0 ;
            int right =n-1;
            int count=0;
            while(count < n*n){
                for(int i = left ; i<=right;i++ ){
                    result[top][i] = ++count;
                }

                for(int i = top+1 ; i<=bottum;i++ ){
                    result[i][right] = ++count;
                }

                for(int i = right-1 ; i>=left && top != bottum;i-- ){
                    result[bottum][i] = ++count;
                }

                for(int i = bottum-1 ; i>=top+1 && left != right ;i-- ){
                    result[i][left] = ++count;
                }
                top++;
                bottum--;
                left++;
                right--;
            }
            return result;
        }
    }


    static class  Solution5 {
        public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
            if(
                    obstacleGrid[obstacleGrid.length-1][obstacleGrid[0].length-1] == 1 ||
                            obstacleGrid[0][0] == 1
            ){
                return 0;
            }

            for(int i = 0 ; i < obstacleGrid.length ; i++ ){
                for(int j = 0 ; j <obstacleGrid[0].length ; j++){
                    if(obstacleGrid[i][j] == 1){
                        obstacleGrid[i][j] = -1;
                    }
                }
            }

            for(int i = 0 ; i < obstacleGrid.length;i++){
                int rowR =  obstacleGrid[i][0];
                if(rowR == 0){
                    obstacleGrid[i][0] = 1;
                }
            }

            for(int i = 0 ; i < obstacleGrid[0].length;i++){
                int colum =  obstacleGrid[0][i];
                if(colum == 0){
                    obstacleGrid[0][i] = 1;
                }
            }

            for(int i = 1 ; i < obstacleGrid.length ; i++ ){
                for(int j = 1 ; j <obstacleGrid[0].length ; j++){
                    if(obstacleGrid[i][j] != -1){
                        int left = obstacleGrid[i-1][j] == -1 ? 0 : obstacleGrid[i-1][j];
                        int top =  obstacleGrid[i][j-1] == -1 ? 0 :  obstacleGrid[i][j-1];
                        obstacleGrid[i][j] = left + top;
                    }
                }
            }

            return obstacleGrid[obstacleGrid.length-1][obstacleGrid[0].length-1];

        }
    }


    static class Solution3 {
        public static List<Integer> getRow(int numRows) {
            //1
            //11
            //121
            //1331
            //2维数组 1. 每行数组的头一个与最后一个都是1  2. 除了第一个的值 = 上一行 + 上一行前一个值
            List<List<Integer>>  list = new ArrayList<>();
            for(int row =0 ; row<numRows;row++){
                List<Integer> columsList = new ArrayList<>();
                for(int colum = 0 ; colum <=row ; colum++){
                    if(colum == 0 || colum == row){
                        columsList.add(1);
                    }else{
                        int result=  list.get(row-1).get(colum) + list.get(row-1).get(colum-1) ;
                        columsList.add(result);
                    }
                }
                list.add(columsList);
            }
            return list.get(2);
        }
    }

    public static void main(String[] args) {
        int[][] params = {{0,1},{0,0}};
        Solution5.uniquePathsWithObstacles(params);
    }

    static class Solution2{
        public void replace(String resource){
            String replace = resource.replace(" ", "%20");
            System.out.println(replace);
        }

        public String replaceByte(String resource){
            char[] chars = resource.toCharArray();
            int length = chars.length;
            for (char aChar : chars) {
                //如果为空格
                if (aChar == 32) {
                    length = length + 1;
                }
            }
            char[] targets = new char[length];

            int sourceIndex = chars.length - 1;
            int targetIndex = length - 1;
            while (targetIndex >= 0) {
                if (chars[sourceIndex] == 32) {
                    targets[targetIndex] = 45;
                    targetIndex--;
                    targets[targetIndex] = 37;
                }else {
                    targets[targetIndex] = chars[sourceIndex];
                }
                targetIndex--;
                sourceIndex--;
            }

            return Arrays.toString(targets);
        }
    }

    class Solution {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            for(int i = 0 ; i < n -1 ; i ++){
                nums1[m + i ] = nums2[i];
            }
            Arrays.sort(nums1);
        }
    }

    class Solution1 {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            int i=m+n-1, j=m-1, k=n-1;
            while(j>=0&&k>=0)
            {
                if (nums1[j] <= nums2[k]) {
                    nums1[i--] = nums2[k--];
                } else if (nums1[j] > nums2[k])
                    nums1[i--] = nums1[j--];
            }
            while(k!=-1)nums1[i--] = nums2[k--];
            while(j!=-1)nums1[i--] = nums1[j--];
        }
    }


    /**
     * 在有序列表中插入元素
     */
    private static void arrayAddTest() {

        int[] arr = new int[20];
        arr[0] = 3;
        arr[1] = 4;
        arr[2] = 7;
        arr[3] = 8;
// 1.中间位置插入
        addByElementSequence(arr, 4, 6);
        printList("在有序数组的中间部分插入元素后的结果为：", arr, 5);
        //此时应输出 3 4 6 7 8

//2.尾部插入
        addByElementSequence(arr, 5, 9);
        printList("在有序数组的尾部插入元素后的结果为：", arr, 6);
        //此时应输出 3 4 6 7 8 9

//3.数组首部插入
        addByElementSequence(arr, 6, 1);
        printList("在有序数组的首部部分插入元素后的结果为：", arr, 7);
        //此时应输出：1 3 4 6 7 8 9

    }

    //todo 作业1：完成这个方法

    /** 有序数组
     * @param arr     存储元素的数组
     * @param size    数组中已经存储的元素数量
     * @param element 要插入数组的新元素
     * @return
     */
    public static void addByElementSequence(int[] arr, int size, int element) {
        //找到下标
        int index = 0 ;
        //最后一个
        if (element >= arr[size - 1]) {
            index = size;
        } else {
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] >= element) {
                    index = i;
                    break;
                }
            }
        }


        //进行复制
        //如果是最后一个位置直接替换就好了
        if (index == arr.length - 1) {
            arr[index] = element;
            return;
        }
        //如果不是则后移动0 1 3
        for (int i = arr.length - 1; i > index; i--) {
            arr[i] = arr[i - 1];
        }
        arr[index] = element;
    }

    /**
     * 删除测试
     */
    private static void deleteTest() {
        int[] arr = new int[]{2, 3, 4, 9, 10, 11, 12};

//1.删除头元素
        removeByElement(arr, 7, 2);
        printList("删除头元素后的结果为：", arr, 6);
        //此时应该打印 3 4 9 10 11 12

//2. 删除尾元素
        removeByElement(arr, 6, 12);
        printList("删除尾元素的结果为：", arr, 5);
        //此时应该打印 3 4 9 10 11

//3. 删除中间元素：
        removeByElement(arr, 5, 9);
        printList("删除中间元素的结果为：", arr, 4);
        //此时应该打印 3 4 10 11
    }

    /**
     * 从数组中删除元素e
     *
     * @param arr
     * @param size 数组已经存放的元素大小
     * @param key  要删除的元素
     */
    public static void removeByElement(int[] arr, int size, int key) {
        int index = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == key) {
                index = i;
                break;
            }
        }
        if (index == -1) {
            return;
        }
        for (int i = index + 1; i < size; i++) {
            arr[i - 1] = arr[i];
        }
        size--;
    }
}
